package HeapSorting;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 均先生
 * Date: 2023-11-18
 * Time: 19:32
 */
public class HeapSorting {
    private static void createHeap(int[] arrray) {
        //构建大根堆
        for (int parent = (arrray.length-1-1)/2;parent >= 0;parent--) {
            siftDown(arrray,parent, arrray.length);
        }
    }

    private static void siftDown(int[] arrray, int parent, int length) {
        int child = 2*parent+1;//这里是指根节点下标默认为0开始,child为左孩子结点
        while (child < length) {
            //child+1为右孩子结点下标.该条件为右孩子下标在数组长度范围内且左孩子的值小于右孩子的值
            if (child+1 < length && arrray[child] < arrray[child+1]) {
                child++;
            }
            //如果孩子结点的值大于双亲结点的值则交换孩子结点和双亲结点
            if (arrray[child] > arrray[parent]) {
                swap(arrray,child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    /**
     * 时间复杂度O(N*logN)
     * 空间复杂度:O(1)
     * 稳定性:不稳定
     * @param array
     */
    public static void heapSort(int[] array) {
        createHeap(array);
        int end = array.length-1;
        //次操作是将堆的最大值拿出来放最后,按从小到大的顺序排列
        while (end > 0) {
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }

    private static void swap(int[] arrray, int i, int j) {
        int tmp = arrray[i];
        arrray[i] = arrray[j];
        arrray[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {4,3,9,6,10,7,8};
        heapSort(array);
         System.out.println(Arrays.toString(array));
    }
}
